{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Flip Equivalent Binary Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: flipEquiv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #翻转等价二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们可以为二叉树 <strong>T</strong> 定义一个&nbsp;<strong>翻转操作&nbsp;</strong>，如下所示：选择任意节点，然后交换它的左子树和右子树。</p>\n",
    "\n",
    "<p>只要经过一定次数的翻转操作后，能使 <strong>X</strong> 等于 <strong>Y</strong>，我们就称二叉树 <strong>X</strong> <em>翻转 等价&nbsp;</em>于二叉树 <strong>Y</strong>。</p>\n",
    "\n",
    "<p>这些树由根节点&nbsp;<code>root1</code> 和 <code>root2</code>&nbsp;给出。如果两个二叉树是否是<em>翻转 等价&nbsp;</em>的函数，则返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"Flipped Trees Diagram\" src=\"https://assets.leetcode.com/uploads/2018/11/29/tree_ex.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>我们翻转值为 1，3 以及 5 的三个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root1 = [], root2 = []\n",
    "<strong>输出:</strong> true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root1 = [], root2 = [1]\n",
    "<strong>输出:</strong> false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每棵树节点数在&nbsp;<code>[0, 100]</code> 范围内</li>\n",
    "\t<li>每棵树中的每个值都是唯一的、在 <code>[0, 99]</code>&nbsp;范围内的整数</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [flip-equivalent-binary-trees](https://leetcode.cn/problems/flip-equivalent-binary-trees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [flip-equivalent-binary-trees](https://leetcode.cn/problems/flip-equivalent-binary-trees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,null,null,null,7,8]\\n[1,3,2,null,6,4,5,null,null,null,null,8,7]', '[]\\n[]', '[]\\n[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 is root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "        return (self.flipEquiv(root1.left, root2.left) and\n",
    "                self.flipEquiv(root1.right, root2.right) or\n",
    "                self.flipEquiv(root1.left, root2.right) and\n",
    "                self.flipEquiv(root1.right, root2.left))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not (root1 or root2): return True\n",
    "        elif root1 and root2:\n",
    "            llrr = self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)\n",
    "            lrlr = self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)\n",
    "            return root1.val == root2.val and (llrr or lrlr) \n",
    "        else: return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 is root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "\n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right) or self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 is root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or (root1.val!=root2.val):\n",
    "            return False\n",
    "\n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \\\n",
    "             (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        if not root1 or not root2:\n",
    "            return False\n",
    "        if root1.val != root2.val :\n",
    "            return False\n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 == root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or (root1.val!=root2.val):\n",
    "            return False\n",
    "\n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \\\n",
    "             (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node1, node2):\n",
    "            if not node1 and not node2: return True\n",
    "            if not node1 or not node2: return False\n",
    "            if node1.val != node2.val: return False\n",
    "            if dfs(node1.left, node2.left) and dfs(node1.right, node2.right): return True\n",
    "            if dfs(node1.left, node2.right) and dfs(node1.right, node2.left): return True\n",
    "            return False\n",
    "        return dfs(root1, root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        if root1 is None or root2 is None:\n",
    "            return False\n",
    "        if root1.val != root2.val:\n",
    "            return False\n",
    "        if ((root1.left is None and root2.left) or (root1.left and root2.left is None)) or (\n",
    "                root1.left and root2.left and root1.left.val != root2.left.val):\n",
    "            root1.left, root1.right = root1.right, root1.left\n",
    "        return self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node1, node2):\n",
    "            if node1 == node2:\n",
    "                return True\n",
    "            if not node1 or not node2 or node1.val != node2.val:\n",
    "                return False\n",
    "            return dfs(node1.left, node2.left) and dfs(node1.right, node2.right) or dfs(node1.left, node2.right) and dfs(node1.right, node2.left)\n",
    "        return dfs(root1, root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def flipEquiv(self, root1, root2):\n",
    "        if root1 is root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "\n",
    "        return (self.flipEquiv(root1.left, root2.left) and\n",
    "                self.flipEquiv(root1.right, root2.right) or\n",
    "                self.flipEquiv(root1.left, root2.right) and\n",
    "                self.flipEquiv(root1.right, root2.left))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        #只要经过一定次数的翻转操作后\n",
    "        #每个node 反转/不反转\n",
    "        def dfs(root1, root2):\n",
    "            if root1 is None and root2 is None:\n",
    "                return True \n",
    "            if root1 is None or root2 is None:\n",
    "                return False \n",
    "            if root1 == root2:\n",
    "                return True \n",
    "            if root1.val != root2.val:\n",
    "                return False \n",
    "            flip =  dfs(root1.left, root2.right)  and dfs(root1.right, root2.left)\n",
    "            not_flip = dfs(root1.left, root2.left) and dfs(root1.right, root2.right)\n",
    "            return flip or not_flip\n",
    "        return dfs(root1, root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 is None and root2 is None:\n",
    "            return True \n",
    "        if root1 is None or root2 is None:return False\n",
    "\n",
    "        if root1.val ==root2.val:\n",
    "            return self.flipEquiv(root1.left,root2.left) and \\\n",
    "            self.flipEquiv(root1.right,root2.right) or \\\n",
    "            self.flipEquiv(root1.left,root2.right) and \\\n",
    "            self.flipEquiv(root1.right,root2.left) \n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 is None and root2 is None:\n",
    "            return True\n",
    "        if (root1 is None and root2 is not None) or (root2 is None and root1 is not None):\n",
    "            return False\n",
    "        if root1.val != root2.val:\n",
    "            return False\n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) \\\n",
    "               or (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 == root2 == None:\n",
    "            return True\n",
    "        if not root1 or not root2 or (root1.val != root2.val):\n",
    "            return False\n",
    "        if self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right):\n",
    "            return True\n",
    "        elif self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        if root1 is root2: return True\n",
    "        if not root1 or not root2 or root1.val != root2.val:return False\n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right) or self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def check(root1,root2):\n",
    "            if not root1 and root2:\n",
    "                return False\n",
    "            if not root2 and root1:\n",
    "                return False\n",
    "            if not root1 and not root2:\n",
    "                return True\n",
    "            if root1.val!=root2.val:\n",
    "                return False\n",
    "            return check(root1.left,root2.left) and check(root1.right,root2.right) or check(root1.left,root2.right) and check(root1.right,root2.left)\n",
    "        return check(root1,root2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        \"\"\"\n",
    "        对于每个结点可能不翻转 可能翻转 只要有一种情况满足即可\n",
    "        \"\"\" \n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        elif not root1 and root2:\n",
    "            return False\n",
    "        elif not root2 and root1:\n",
    "            return False\n",
    "        elif root1.val != root2.val:\n",
    "            return False\n",
    "        else:\n",
    "            case = self.flipEquiv(root1.left,root2.left) and self.flipEquiv(root1.right,root2.right) #不翻转\n",
    "            if case:\n",
    "                return True\n",
    "            return self.flipEquiv(root1.right,root2.left) and self.flipEquiv(root1.left,root2.right) #翻转\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "        \n",
    "        return self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right) or self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 or not root2:\n",
    "            return root1 == root2\n",
    "        #从最底层开始,逐个往上验证\n",
    "        #先写一个层序遍历\n",
    "        res = []\n",
    "        def read(root, fa = 0): #root 是 [root] 这层都在了, fa是父值\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return\n",
    "            # res += [r.val for r in root],\n",
    "            nxt = []\n",
    "            res += [set()]\n",
    "            while root:\n",
    "                tem = root.pop()\n",
    "                if tem.left:\n",
    "                    nxt += tem.left,\n",
    "                    res[-1].add((tem.val,tem.left.val))\n",
    "                if tem.right:\n",
    "                    nxt += tem.right,\n",
    "                    res[-1].add((tem.val,tem.right.val))\n",
    "            read(nxt,fa+1)\n",
    "        read([root1])\n",
    "        # print(res)\n",
    "        tem = res.copy()\n",
    "        res = []\n",
    "        read([root2])\n",
    "        # print(tem)\n",
    "        # print(res)\n",
    "        return tem == res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        if not root1 or not root2:\n",
    "            return False\n",
    "        if root1.val != root2.val:\n",
    "            return False\n",
    "        ll = self.flipEquiv(root1.left, root2.left)\n",
    "        rr = self.flipEquiv(root1.right, root2.right)\n",
    "        lr = self.flipEquiv(root1.left, root2.right)\n",
    "        rl = self.flipEquiv(root1.right, root2.left)\n",
    "        if (ll and rr) or (lr and rl):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def check(root1,root2):\n",
    "            if not root1 and root2:\n",
    "                return False\n",
    "            if not root2 and root1:\n",
    "                return False\n",
    "            if not root1 and not root2:\n",
    "                return True\n",
    "            if root1.val!=root2.val:\n",
    "                return False\n",
    "            return check(root1.left,root2.left) and check(root1.right,root2.right) or check(root1.left,root2.right) and check(root1.right,root2.left)\n",
    "        return check(root1,root2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        if not root1 or not root2:\n",
    "            return False\n",
    "        if root1.val != root2.val:\n",
    "            return False\n",
    "        ll = self.flipEquiv(root1.left, root2.left)\n",
    "        rr = self.flipEquiv(root1.right, root2.right)\n",
    "        lr = self.flipEquiv(root1.left, root2.right)\n",
    "        rl = self.flipEquiv(root1.right, root2.left)\n",
    "        if (ll and rr) or (lr and rl):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        def g(r,l):\n",
    "          if r is None and l is None:\n",
    "              return True      \n",
    "          if (r and l and r.val !=l.val) or not(r and l):\n",
    "             return False\n",
    "          c=min(g(r.left,l.left),g(r.right,l.right))\n",
    "          y=min(g(r.right,l.left),g(r.left,l.right))\n",
    "          return c or y\n",
    "        return g(root1,root2)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "\n",
    "\n",
    "        if root1 is None and root2 is None:\n",
    "            return True \n",
    "        if root1 is None or root2 is None:return False\n",
    "\n",
    "        if root1.val ==root2.val:\n",
    "            \n",
    "            return self.flipEquiv(root1.left,root2.left) and \\\n",
    "            self.flipEquiv(root1.right,root2.right) or \\\n",
    "            self.flipEquiv(root1.left,root2.right) and \\\n",
    "            self.flipEquiv(root1.right,root2.left) \n",
    "            \n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # copy from: https://leetcode.cn/problems/flip-equivalent-binary-trees/discussion/comments/226508\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 is None and root2 is None:\n",
    "            return True\n",
    "        if root1 is None or root2 is None:\n",
    "            return False\n",
    "        if root1.val != root2.val:\n",
    "            return False\n",
    "        # LL && RR\n",
    "        # LR && RL\n",
    "        a = self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)\n",
    "        b = self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)\n",
    "        return a or b\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def check(root1,root2):\n",
    "            if not root1 and root2:\n",
    "                return False\n",
    "            if not root2 and root1:\n",
    "                return False\n",
    "            if not root1 and not root2:\n",
    "                return True\n",
    "            if root1.val!=root2.val:\n",
    "                return False\n",
    "            return check(root1.left,root2.left) and check(root1.right,root2.right) or check(root1.left,root2.right) and check(root1.right,root2.left)\n",
    "        return check(root1,root2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1, root2):\n",
    "        if (not root1) and (not root2):\n",
    "            return True\n",
    "        elif (not root1) and root2:\n",
    "            return False\n",
    "        elif root1 and (not root2):\n",
    "            return False\n",
    "        elif root1.val != root2.val:\n",
    "            return False\n",
    "        queue = []\n",
    "\n",
    "        queue.append([root1, root2])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if (not node[0]) or (not node[1]):\n",
    "                continue\n",
    "            if not node[0].left:\n",
    "                node[0].left = TreeNode(\"#\")\n",
    "            if not node[1].left:\n",
    "                node[1].left = TreeNode(\"#\")\n",
    "            if not node[0].right:\n",
    "                node[0].right = TreeNode(\"#\")\n",
    "            if not node[1].right:\n",
    "                node[1].right = TreeNode(\"#\")\n",
    "\n",
    "            if node[0].left.val != node[1].left.val:\n",
    "                tmp = node[0].left\n",
    "                node[0].left = node[0].right\n",
    "                node[0].right = tmp\n",
    "                if node[0].left.val != node[1].left.val:\n",
    "                    return False\n",
    "            if node[0].right.val != node[1].right.val:\n",
    "                return False\n",
    "\n",
    "            if node[0].left.val != \"#\" and node[1].left.val != \"#\":\n",
    "                queue.append([node[0].left, node[1].left])\n",
    "            if node[0].right.val != \"#\" and node[1].right.val != \"#\":\n",
    "                queue.append([node[0].right, node[1].right])\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 is root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "\n",
    "        return (self.flipEquiv(root1.left, root2.left) and\n",
    "                self.flipEquiv(root1.right, root2.right) or\n",
    "                self.flipEquiv(root1.left, root2.right) and\n",
    "                self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 == root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "        \n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 is root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) \\\n",
    "                or (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))\n",
    "\n",
    "\n",
    "\n",
    "        # def dfs(node):\n",
    "        #     if node:\n",
    "        #         yield node.val\n",
    "        #         L = node.left.val if node.left else -1\n",
    "        #         R = node.right.val if node.right else -1\n",
    "        #         if L < R:\n",
    "        #             yield from dfs(node.left)\n",
    "        #             yield from dfs(node.right)\n",
    "        #         else:\n",
    "        #             yield from dfs(node.right)\n",
    "        #             yield from dfs(node.left)\n",
    "        #         yield '#'\n",
    "        # return all(x == y for x, y in itertools.zip_longest(\n",
    "        #     dfs(root1), dfs(root2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        if not root1 and root2:\n",
    "            return False\n",
    "        if not root2 and root1:\n",
    "            return False\n",
    "        if root1.val == root2.val:\n",
    "            return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        elif not root1 or not root2:\n",
    "            return False\n",
    "        if root1.val != root2.val:\n",
    "            return False\n",
    "        return (self.flipEquiv(root1.right, root2.right) and self.flipEquiv(root1.left, root2.left)) or (self.flipEquiv(root1.right, root2.left) and self.flipEquiv(root1.left, root2.right))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        return self.compare(root1, root2)\n",
    "    \n",
    "    def compare(self, root1, root2):\n",
    "        if not root1:\n",
    "            if not root2:\n",
    "                return True\n",
    "            return False\n",
    "        if not root2:\n",
    "            return False\n",
    "        if root1.val != root2.val:\n",
    "            return False\n",
    "        return (self.compare(root1.left, root2.left) or self.compare(root1.left, root2.right)) and (\n",
    "            self.compare(root1.right, root2.left) or self.compare(root1.right, root2.right)\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        if root1 is root2: return True\n",
    "\n",
    "        if not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "        \n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right) or self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\r\n",
    "        if not root1 and not root2:\r\n",
    "            return True\r\n",
    "        elif not root1 or not root2 or root1.val != root2.val:\r\n",
    "            return False\r\n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \\\r\n",
    "            (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def flipEquiv(self, root1, root2):\n",
    "        if root1 is root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "\n",
    "        return (self.flipEquiv(root1.left, root2.left) and\n",
    "                self.flipEquiv(root1.right, root2.right) or\n",
    "                self.flipEquiv(root1.left, root2.right) and\n",
    "                self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2:\n",
    "                return True\n",
    "        elif not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "        \n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def check(root1,root2):\n",
    "            if not root1 and root2:\n",
    "                return False\n",
    "            if not root2 and root1:\n",
    "                return False\n",
    "            if not root1 and not root2:\n",
    "                return True\n",
    "            if root1.val!=root2.val:\n",
    "                return False\n",
    "            return check(root1.left,root2.left) and check(root1.right,root2.right) or check(root1.left,root2.right) and check(root1.right,root2.left)\n",
    "        return check(root1,root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 == root2:\n",
    "            return True\n",
    "        if root1 is None or root2 is None:\n",
    "            return root1 == None and root2 == None\n",
    "        if root1.val != root2.val:\n",
    "            return False\n",
    "        \n",
    "        return self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left) or self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 == None and root2 == None:\n",
    "            return True\n",
    "        elif root1 == None or root2 == None:\n",
    "            return False\n",
    "        else:\n",
    "            # print(root1.val, root2.val)\n",
    "            if root1.val == root2.val:\n",
    "                if self.flipEquiv(root1.left,root2.right) and self.flipEquiv(root1.right,root2.left):\n",
    "                    return True\n",
    "                elif self.flipEquiv(root1.left,root2.left) and self.flipEquiv(root1.right,root2.right):\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                 return False\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 is root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or root1.val!=root2.val:\n",
    "            return False\n",
    "        return (self.flipEquiv(root1.left,root2.left) and self.flipEquiv(root1.right,root2.right) or self.flipEquiv(root1.left,root2.right) and self.flipEquiv(root1.right,root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2: return True\n",
    "        if not root1 or not root2: return False\n",
    "        if root1.val!=root2.val: return False\n",
    "        res=self.flipEquiv(root1.left,root2.left) and self.flipEquiv(root1.right,root2.right)\n",
    "        if res: return True\n",
    "        return self.flipEquiv(root1.left,root2.right) and self.flipEquiv(root1.right,root2.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def check(root1,root2):\n",
    "            if not root1 and root2:\n",
    "                return False\n",
    "            if not root2 and root1:\n",
    "                return False\n",
    "            if not root1 and not root2:\n",
    "                return True\n",
    "            if root1.val!=root2.val:\n",
    "                return False\n",
    "            return check(root1.left,root2.left) and check(root1.right,root2.right) or check(root1.left,root2.right) and check(root1.right,root2.left)\n",
    "        return check(root1,root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        return True if (root1 is None and root2 is None) else False if (root1 is None or root2 is None) else True if (root1.val == root2.val and (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right) or self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))) else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        def bfs(root):\n",
    "            q = deque([root])\n",
    "            l, c = defaultdict(set), defaultdict(set)\n",
    "            level = 0\n",
    "            if root:\n",
    "                while q:\n",
    "                    num = len(q)\n",
    "                    for _ in range(num):\n",
    "                        node = q.popleft()\n",
    "                        l[level].add(node.val)\n",
    "                        if node.left:\n",
    "                            c[node.val].add(node.left.val)\n",
    "                            q.append(node.left)\n",
    "                        if node.right:\n",
    "                            c[node.val].add(node.right.val)\n",
    "                            q.append(node.right)\n",
    "                    level += 1\n",
    "            return l, c\n",
    "        \n",
    "        l1, c1 = bfs(root1)\n",
    "        l2, c2 = bfs(root2)\n",
    "        return l1 == l2 and c1 == c2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def flip(root1,root2):\n",
    "            if root1 == None and root2 == None:\n",
    "                return True\n",
    "            if root1 == None or root2 == None:\n",
    "                return False\n",
    "            #两种情况：需要反转/不需要翻转\n",
    "            return root1.val == root2.val and ( ((flip(root1.left,root2.left) and flip(root1.right,root2.right)))  or ((flip(root1.left,root2.right) and flip(root1.right,root2.left))) )\n",
    "\n",
    "        return flip(root1,root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: TreeNode | None, root2: TreeNode | None) -> bool:\n",
    "        if root1 is None and root2 is None:\n",
    "            return True\n",
    "        elif root1 is None or root2 is None:\n",
    "            return False\n",
    "        else:\n",
    "            return root1.val == root2.val and (\n",
    "                (\n",
    "                    self.flipEquiv(root1.left, root2.left)\n",
    "                    and self.flipEquiv(root1.right, root2.right)\n",
    "                )\n",
    "                or (\n",
    "                    self.flipEquiv(root1.left, root2.right)\n",
    "                    and self.flipEquiv(root1.right, root2.left)\n",
    "                )\n",
    "            )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        # 只要左右结点相等或者左等于右既可以作为认为是相等\n",
    "        def dfs(root1, root2):\n",
    "            if not root1 and not root2:\n",
    "                return True\n",
    "            if not (root1 and root2):\n",
    "                return False\n",
    "            if root1.val != root2.val:\n",
    "                return False\n",
    "            return (dfs(root1.left, root2.left) and dfs(root1.right, root2.right)) or (dfs(root1.left, root2.right) and dfs(root1.right, root2.left))\n",
    "        return dfs(root1, root2)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if root1 is root2:\n",
    "            return True\n",
    "        if not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "        \n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        return self.is_flip_equiv(root1, root2)\n",
    "\n",
    "    def is_flip_equiv(self, tree1, tree2):\n",
    "        if not tree1:\n",
    "            if not tree2:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            if not tree2:\n",
    "                return False\n",
    "        if tree1.val != tree2.val:\n",
    "            return False\n",
    "        tree1_leaves, tree2_leaves = 0, 0\n",
    "        if tree1.left: tree1_leaves+=1\n",
    "        if tree1.right: tree1_leaves+=1\n",
    "        if tree2.left: tree2_leaves+=1\n",
    "        if tree2.right: tree2_leaves+=1\n",
    "\n",
    "        if tree1_leaves!=tree2_leaves: return False\n",
    "\n",
    "        if tree1_leaves==0:\n",
    "            if tree1.val == tree2.val:\n",
    "                return True\n",
    "        elif tree1_leaves==1:\n",
    "            if tree1.left:\n",
    "                if tree2.left:\n",
    "                    return self.is_flip_equiv(tree1.left, tree2.left)\n",
    "                else:\n",
    "                    return self.is_flip_equiv(tree1.left, tree2.right)\n",
    "            else:\n",
    "                if tree2.left:\n",
    "                    return self.is_flip_equiv(tree1.right, tree2.left)\n",
    "                else:\n",
    "                    return self.is_flip_equiv(tree1.right, tree2.right)\n",
    "        else:\n",
    "            flip1 = self.is_flip_equiv(tree1.left, tree2.left) and self.is_flip_equiv(tree1.right, tree2.right)\n",
    "            flip2 = self.is_flip_equiv(tree1.left, tree2.right) and self.is_flip_equiv(tree1.right, tree2.left)\n",
    "            return (flip1 or flip2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2:\n",
    "            return True \n",
    "        if root1 is root2:\n",
    "            return True\n",
    "            \n",
    "        if (not root1 or not root2) or (root1.val != root2.val):\n",
    "            return False\n",
    "\n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right) or\n",
    "                self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2: return True\n",
    "        if (not root1 and root2) or (not root2 and root1):\n",
    "            return False\n",
    "\n",
    "        if root1.val != root2.val: return False\n",
    "        dis = self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)\n",
    "        flip = self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)\n",
    "        return dis or flip"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        if (root1 and not root2) or (root2 and not root1) or root1.val != root2.val:\n",
    "            return False\n",
    "\n",
    "        return (self.flipEquiv(root1.left,root2.left) and self.flipEquiv(root1.right,root2.right)) or self.flipEquiv(root1.left,root2.right) and self.flipEquiv(root1.right,root2.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2: return True\n",
    "        if (not root1 and root2) or (not root2 and root1): return False\n",
    "        if root1.val != root2.val: return False\n",
    "        dis = self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)\n",
    "        flip = self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)\n",
    "        return dis or flip"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        if not root1 or not root2:\n",
    "            return False\n",
    "        if root1.val != root2.val:\n",
    "            return False\n",
    "        not_invert = self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)\n",
    "        invert = self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)\n",
    "        return not_invert or invert\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        # if both nodes are None\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        # if one of the nodes is None or values are different\n",
    "        if not root1 or not root2 or root1.val != root2.val:\n",
    "            return False\n",
    "        # check if children are flip equivalent\n",
    "        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \\\n",
    "               (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        @cache\n",
    "        def f(i,j):\n",
    "            if i is None and j is None:\n",
    "                return True\n",
    "            elif j is None:\n",
    "                return False\n",
    "            elif i is None:\n",
    "                return False\n",
    "            if i.val == j.val:\n",
    "                return (f(i.left,j.left) and f(i.right,j.right)) or (f(i.right,j.left) and f(i.left,j.right))\n",
    "            else:\n",
    "                return False\n",
    "        return f(root1,root2)\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
